/***************************************************************************/
/*                                                                         */
/*  ftdbgmem.c                                                             */
/*                                                                         */
/*    Memory debugger (body).                                              */
/*                                                                         */
/*  Copyright 2001, 2002, 2003, 2004, 2005, 2006, 2009 by                  */
/*  David Turner, Robert Wilhelm, and Werner Lemberg.                      */
/*                                                                         */
/*  This file is part of the FreeType project, and may only be used,       */
/*  modified, and distributed under the terms of the FreeType project      */
/*  license, LICENSE.TXT.  By continuing to use, modify, or distribute     */
/*  this file you indicate that you have read the license and              */
/*  understand and accept it fully.                                        */
/*                                                                         */
/***************************************************************************/


#include <ft2build.h>
#include FT_CONFIG_CONFIG_H
#include FT_INTERNAL_DEBUG_H
#include FT_INTERNAL_MEMORY_H
#include FT_SYSTEM_H
#include FT_ERRORS_H
#include FT_TYPES_H


#ifdef FT_DEBUG_MEMORY

#define  KEEPALIVE /* `Keep alive' means that freed blocks aren't released
* to the heap.  This is useful to detect double-frees
* or weird heap corruption, but it uses large amounts of
* memory, however.
*/

#include FT_CONFIG_STANDARD_LIBRARY_H

FT_BASE_DEF( const char* )  _ft_debug_file   = 0;
FT_BASE_DEF( long )         _ft_debug_lineno = 0;

extern void
FT_DumpMemory( FT_Memory  memory );


typedef struct FT_MemSourceRec_*  FT_MemSource;
typedef struct FT_MemNodeRec_*    FT_MemNode;
typedef struct FT_MemTableRec_*   FT_MemTable;


#define FT_MEM_VAL( addr )  ((FT_PtrDist)(FT_Pointer)( addr ))

/*
*  This structure holds statistics for a single allocation/release
*  site.  This is useful to know where memory operations happen the
*  most.
*/
typedef struct  FT_MemSourceRec_
{
const char*   file_name;
long          line_no;

FT_Long       cur_blocks;   /* current number of allocated blocks */
FT_Long       max_blocks;   /* max. number of allocated blocks    */
FT_Long       all_blocks;   /* total number of blocks allocated   */

FT_Long       cur_size;     /* current cumulative allocated size */
FT_Long       max_size;     /* maximum cumulative allocated size */
FT_Long       all_size;     /* total cumulative allocated size   */

FT_Long       cur_max;      /* current maximum allocated size */

FT_UInt32     hash;
FT_MemSource  link;

} FT_MemSourceRec;


/*
*  We don't need a resizable array for the memory sources, because
*  their number is pretty limited within FreeType.
*/
#define FT_MEM_SOURCE_BUCKETS  128

/*
*  This structure holds information related to a single allocated
*  memory block.  If KEEPALIVE is defined, blocks that are freed by
*  FreeType are never released to the system.  Instead, their `size'
*  field is set to -size.  This is mainly useful to detect double frees,
*  at the price of large memory footprint during execution.
*/
typedef struct  FT_MemNodeRec_
{
FT_Byte*      address;
FT_Long       size;     /* < 0 if the block was freed */

FT_MemSource  source;

#ifdef KEEPALIVE
const char*   free_file_name;
FT_Long       free_line_no;
#endif

FT_MemNode    link;

} FT_MemNodeRec;


/*
*  The global structure, containing compound statistics and all hash
*  tables.
*/
typedef struct  FT_MemTableRec_
{
FT_ULong         size;
FT_ULong         nodes;
FT_MemNode*      buckets;

FT_ULong         alloc_total;
FT_ULong         alloc_current;
FT_ULong         alloc_max;
FT_ULong         alloc_count;

FT_Bool          bound_total;
FT_ULong         alloc_total_max;

FT_Bool          bound_count;
FT_ULong         alloc_count_max;

FT_MemSource     sources[FT_MEM_SOURCE_BUCKETS];

FT_Bool          keep_alive;

FT_Memory        memory;
FT_Pointer       memory_user;
FT_Alloc_Func    alloc;
FT_Free_Func     free;
FT_Realloc_Func  realloc;

} FT_MemTableRec;


#define FT_MEM_SIZE_MIN  7
#define FT_MEM_SIZE_MAX  13845163

#define FT_FILENAME( x )  ((x) ? (x) : "unknown file")


/*
*  Prime numbers are ugly to handle.  It would be better to implement
*  L-Hashing, which is 10% faster and doesn't require divisions.
*/
static const FT_UInt  ft_mem_primes[] =
{
7,
11,
19,
37,
73,
109,
163,
251,
367,
557,
823,
1237,
1861,
2777,
4177,
6247,
9371,
14057,
21089,
31627,
47431,
71143,
106721,
160073,
240101,
360163,
540217,
810343,
1215497,
1823231,
2734867,
4102283,
6153409,
9230113,
13845163,
};


static FT_ULong
ft_mem_closest_prime( FT_ULong  num )
{
FT_UInt  i;


for ( i = 0;
i < sizeof ( ft_mem_primes ) / sizeof ( ft_mem_primes[0] ); i++ )
if ( ft_mem_primes[i] > num )
return ft_mem_primes[i];

return FT_MEM_SIZE_MAX;
}


extern void
ft_mem_debug_panic( const char*  fmt,
  ... )
{
va_list  ap;


printf( "FreeType.Debug: " );

va_start( ap, fmt );
vprintf( fmt, ap );
va_end( ap );

printf( "\n" );
exit( EXIT_FAILURE );
}


static FT_Pointer
ft_mem_table_alloc( FT_MemTable  table,
  FT_Long      size )
{
FT_Memory   memory = table->memory;
FT_Pointer  block;


memory->user = table->memory_user;
block = table->alloc( memory, size );
memory->user = table;

return block;
}


static void
ft_mem_table_free( FT_MemTable  table,
 FT_Pointer   block )
{
FT_Memory  memory = table->memory;


memory->user = table->memory_user;
table->free( memory, block );
memory->user = table;
}


static void
ft_mem_table_resize( FT_MemTable  table )
{
FT_ULong  new_size;


new_size = ft_mem_closest_prime( table->nodes );
if ( new_size != table->size )
{
FT_MemNode*  new_buckets;
FT_ULong     i;


new_buckets = (FT_MemNode *)
  ft_mem_table_alloc( table,
                      new_size * sizeof ( FT_MemNode ) );
if ( new_buckets == NULL )
return;

FT_ARRAY_ZERO( new_buckets, new_size );

for ( i = 0; i < table->size; i++ )
{
FT_MemNode  node, next, *pnode;
FT_PtrDist  hash;


node = table->buckets[i];
while ( node )
{
next  = node->link;
hash  = FT_MEM_VAL( node->address ) % new_size;
pnode = new_buckets + hash;

node->link = pnode[0];
pnode[0]   = node;

node = next;
}
}

if ( table->buckets )
ft_mem_table_free( table, table->buckets );

table->buckets = new_buckets;
table->size    = new_size;
}
}


static FT_MemTable
ft_mem_table_new( FT_Memory  memory )
{
FT_MemTable  table;


table = (FT_MemTable)memory->alloc( memory, sizeof ( *table ) );
if ( table == NULL )
goto Exit;

FT_ZERO( table );

table->size  = FT_MEM_SIZE_MIN;
table->nodes = 0;

table->memory = memory;

table->memory_user = memory->user;

table->alloc   = memory->alloc;
table->realloc = memory->realloc;
table->free    = memory->free;

table->buckets = (FT_MemNode *)
   memory->alloc( memory,
                  table->size * sizeof ( FT_MemNode ) );
if ( table->buckets )
FT_ARRAY_ZERO( table->buckets, table->size );
else
{
memory->free( memory, table );
table = NULL;
}

Exit:
return table;
}


static void
ft_mem_table_destroy( FT_MemTable  table )
{
FT_ULong  i;


FT_DumpMemory( table->memory );

if ( table )
{
FT_Long   leak_count = 0;
FT_ULong  leaks      = 0;


/* remove all blocks from the table, revealing leaked ones */
for ( i = 0; i < table->size; i++ )
{
FT_MemNode  *pnode = table->buckets + i, next, node = *pnode;


while ( node )
{
next       = node->link;
node->link = 0;

if ( node->size > 0 )
{
printf(
"leaked memory block at address %p, size %8ld in (%s:%ld)\n",
node->address, node->size,
FT_FILENAME( node->source->file_name ),
node->source->line_no );

leak_count++;
leaks += node->size;

ft_mem_table_free( table, node->address );
}

node->address = NULL;
node->size    = 0;

ft_mem_table_free( table, node );
node = next;
}
table->buckets[i] = 0;
}

ft_mem_table_free( table, table->buckets );
table->buckets = NULL;

table->size  = 0;
table->nodes = 0;

/* remove all sources */
for ( i = 0; i < FT_MEM_SOURCE_BUCKETS; i++ )
{
FT_MemSource  source, next;


for ( source = table->sources[i]; source != NULL; source = next )
{
next = source->link;
ft_mem_table_free( table, source );
}

table->sources[i] = NULL;
}

printf(
"FreeType: total memory allocations = %ld\n", table->alloc_total );
printf(
"FreeType: maximum memory footprint = %ld\n", table->alloc_max );

ft_mem_table_free( table, table );

if ( leak_count > 0 )
ft_mem_debug_panic(
"FreeType: %ld bytes of memory leaked in %ld blocks\n",
leaks, leak_count );

printf( "FreeType: no memory leaks detected\n" );
}
}


static FT_MemNode*
ft_mem_table_get_nodep( FT_MemTable  table,
      FT_Byte*     address )
{
FT_PtrDist   hash;
FT_MemNode  *pnode, node;


hash  = FT_MEM_VAL( address );
pnode = table->buckets + ( hash % table->size );

for (;;)
{
node = pnode[0];
if ( !node )
break;

if ( node->address == address )
break;

pnode = &node->link;
}
return pnode;
}


static FT_MemSource
ft_mem_table_get_source( FT_MemTable  table )
{
FT_UInt32     hash;
FT_MemSource  node, *pnode;


/* cast to FT_PtrDist first since void* can be larger */
/* than FT_UInt32 and GCC 4.1.1 emits a warning       */
hash  = (FT_UInt32)(FT_PtrDist)(void*)_ft_debug_file +
(FT_UInt32)( 5 * _ft_debug_lineno );
pnode = &table->sources[hash % FT_MEM_SOURCE_BUCKETS];

for ( ;; )
{
node = *pnode;
if ( node == NULL )
break;

if ( node->file_name == _ft_debug_file &&
node->line_no   == _ft_debug_lineno   )
goto Exit;

pnode = &node->link;
}

node = (FT_MemSource)ft_mem_table_alloc( table, sizeof ( *node ) );
if ( node == NULL )
ft_mem_debug_panic(
"not enough memory to perform memory debugging\n" );

node->file_name = _ft_debug_file;
node->line_no   = _ft_debug_lineno;

node->cur_blocks = 0;
node->max_blocks = 0;
node->all_blocks = 0;

node->cur_size   = 0;
node->max_size   = 0;
node->all_size   = 0;

node->cur_max    = 0;

node->link = NULL;
node->hash = hash;
*pnode     = node;

Exit:
return node;
}


static void
ft_mem_table_set( FT_MemTable  table,
FT_Byte*     address,
FT_ULong     size,
FT_Long      delta )
{
FT_MemNode  *pnode, node;


if ( table )
{
FT_MemSource  source;


pnode = ft_mem_table_get_nodep( table, address );
node  = *pnode;
if ( node )
{
if ( node->size < 0 )
{
/* This block was already freed.  Our memory is now completely */
/* corrupted!                                                  */
/* This can only happen in keep-alive mode.                    */
ft_mem_debug_panic(
"memory heap corrupted (allocating freed block)" );
}
else
{
/* This block was already allocated.  This means that our memory */
/* is also corrupted!                                            */
ft_mem_debug_panic(
"memory heap corrupted (re-allocating allocated block at"
" %p, of size %ld)\n"
"org=%s:%d new=%s:%d\n",
node->address, node->size,
FT_FILENAME( node->source->file_name ), node->source->line_no,
FT_FILENAME( _ft_debug_file ), _ft_debug_lineno );
}
}

/* we need to create a new node in this table */
node = (FT_MemNode)ft_mem_table_alloc( table, sizeof ( *node ) );
if ( node == NULL )
ft_mem_debug_panic( "not enough memory to run memory tests" );

node->address = address;
node->size    = size;
node->source  = source = ft_mem_table_get_source( table );

if ( delta == 0 )
{
/* this is an allocation */
source->all_blocks++;
source->cur_blocks++;
if ( source->cur_blocks > source->max_blocks )
source->max_blocks = source->cur_blocks;
}

if ( size > (FT_ULong)source->cur_max )
source->cur_max = size;

if ( delta != 0 )
{
/* we are growing or shrinking a reallocated block */
source->cur_size     += delta;
table->alloc_current += delta;
}
else
{
/* we are allocating a new block */
source->cur_size     += size;
table->alloc_current += size;
}

source->all_size += size;

if ( source->cur_size > source->max_size )
source->max_size = source->cur_size;

node->free_file_name = NULL;
node->free_line_no   = 0;

node->link = pnode[0];

pnode[0] = node;
table->nodes++;

table->alloc_total += size;

if ( table->alloc_current > table->alloc_max )
table->alloc_max = table->alloc_current;

if ( table->nodes * 3 < table->size  ||
table->size  * 3 < table->nodes )
ft_mem_table_resize( table );
}
}


static void
ft_mem_table_remove( FT_MemTable  table,
   FT_Byte*     address,
   FT_Long      delta )
{
if ( table )
{
FT_MemNode  *pnode, node;


pnode = ft_mem_table_get_nodep( table, address );
node  = *pnode;
if ( node )
{
FT_MemSource  source;


if ( node->size < 0 )
ft_mem_debug_panic(
"freeing memory block at %p more than once at (%s:%ld)\n"
"block allocated at (%s:%ld) and released at (%s:%ld)",
address,
FT_FILENAME( _ft_debug_file ), _ft_debug_lineno,
FT_FILENAME( node->source->file_name ), node->source->line_no,
FT_FILENAME( node->free_file_name ), node->free_line_no );

/* scramble the node's content for additional safety */
FT_MEM_SET( address, 0xF3, node->size );

if ( delta == 0 )
{
source = node->source;

source->cur_blocks--;
source->cur_size -= node->size;

table->alloc_current -= node->size;
}

if ( table->keep_alive )
{
/* we simply invert the node's size to indicate that the node */
/* was freed.                                                 */
node->size           = -node->size;
node->free_file_name = _ft_debug_file;
node->free_line_no   = _ft_debug_lineno;
}
else
{
table->nodes--;

*pnode = node->link;

node->size   = 0;
node->source = NULL;

ft_mem_table_free( table, node );

if ( table->nodes * 3 < table->size  ||
table->size  * 3 < table->nodes )
ft_mem_table_resize( table );
}
}
else
ft_mem_debug_panic(
"trying to free unknown block at %p in (%s:%ld)\n",
address,
FT_FILENAME( _ft_debug_file ), _ft_debug_lineno );
}
}


extern FT_Pointer
ft_mem_debug_alloc( FT_Memory  memory,
  FT_Long    size )
{
FT_MemTable  table = (FT_MemTable)memory->user;
FT_Byte*     block;


if ( size <= 0 )
ft_mem_debug_panic( "negative block size allocation (%ld)", size );

/* return NULL if the maximum number of allocations was reached */
if ( table->bound_count                           &&
table->alloc_count >= table->alloc_count_max )
return NULL;

/* return NULL if this allocation would overflow the maximum heap size */
if ( table->bound_total                                             &&
table->alloc_total_max - table->alloc_current > (FT_ULong)size )
return NULL;

block = (FT_Byte *)ft_mem_table_alloc( table, size );
if ( block )
{
ft_mem_table_set( table, block, (FT_ULong)size, 0 );

table->alloc_count++;
}

_ft_debug_file   = "<unknown>";
_ft_debug_lineno = 0;

return (FT_Pointer)block;
}


extern void
ft_mem_debug_free( FT_Memory   memory,
 FT_Pointer  block )
{
FT_MemTable  table = (FT_MemTable)memory->user;


if ( block == NULL )
ft_mem_debug_panic( "trying to free NULL in (%s:%ld)",
      FT_FILENAME( _ft_debug_file ),
      _ft_debug_lineno );

ft_mem_table_remove( table, (FT_Byte*)block, 0 );

if ( !table->keep_alive )
ft_mem_table_free( table, block );

table->alloc_count--;

_ft_debug_file   = "<unknown>";
_ft_debug_lineno = 0;
}


extern FT_Pointer
ft_mem_debug_realloc( FT_Memory   memory,
    FT_Long     cur_size,
    FT_Long     new_size,
    FT_Pointer  block )
{
FT_MemTable  table = (FT_MemTable)memory->user;
FT_MemNode   node, *pnode;
FT_Pointer   new_block;
FT_Long      delta;

const char*  file_name = FT_FILENAME( _ft_debug_file );
FT_Long      line_no   = _ft_debug_lineno;


/* unlikely, but possible */
if ( new_size == cur_size )
return block;

/* the following is valid according to ANSI C */
#if 0
if ( block == NULL || cur_size == 0 )
ft_mem_debug_panic( "trying to reallocate NULL in (%s:%ld)",
      file_name, line_no );
#endif

/* while the following is allowed in ANSI C also, we abort since */
/* such case should be handled by FreeType.                      */
if ( new_size <= 0 )
ft_mem_debug_panic(
"trying to reallocate %p to size 0 (current is %ld) in (%s:%ld)",
block, cur_size, file_name, line_no );

/* check `cur_size' value */
pnode = ft_mem_table_get_nodep( table, (FT_Byte*)block );
node  = *pnode;
if ( !node )
ft_mem_debug_panic(
"trying to reallocate unknown block at %p in (%s:%ld)",
block, file_name, line_no );

if ( node->size <= 0 )
ft_mem_debug_panic(
"trying to reallocate freed block at %p in (%s:%ld)",
block, file_name, line_no );

if ( node->size != cur_size )
ft_mem_debug_panic( "invalid ft_realloc request for %p. cur_size is "
      "%ld instead of %ld in (%s:%ld)",
      block, cur_size, node->size, file_name, line_no );

/* return NULL if the maximum number of allocations was reached */
if ( table->bound_count                           &&
table->alloc_count >= table->alloc_count_max )
return NULL;

delta = (FT_Long)( new_size - cur_size );

/* return NULL if this allocation would overflow the maximum heap size */
if ( delta > 0                                                       &&
table->bound_total                                              &&
table->alloc_current + (FT_ULong)delta > table->alloc_total_max )
return NULL;

new_block = (FT_Byte *)ft_mem_table_alloc( table, new_size );
if ( new_block == NULL )
return NULL;

ft_mem_table_set( table, (FT_Byte*)new_block, new_size, delta );

ft_memcpy( new_block, block, cur_size < new_size ? cur_size : new_size );

ft_mem_table_remove( table, (FT_Byte*)block, delta );

_ft_debug_file   = "<unknown>";
_ft_debug_lineno = 0;

if ( !table->keep_alive )
ft_mem_table_free( table, block );

return new_block;
}


extern FT_Int
ft_mem_debug_init( FT_Memory  memory )
{
FT_MemTable  table;
FT_Int       result = 0;


if ( getenv( "FT2_DEBUG_MEMORY" ) )
{
table = ft_mem_table_new( memory );
if ( table )
{
const char*  p;


memory->user    = table;
memory->alloc   = ft_mem_debug_alloc;
memory->realloc = ft_mem_debug_realloc;
memory->free    = ft_mem_debug_free;

p = getenv( "FT2_ALLOC_TOTAL_MAX" );
if ( p != NULL )
{
FT_Long   total_max = ft_atol( p );


if ( total_max > 0 )
{
table->bound_total     = 1;
table->alloc_total_max = (FT_ULong)total_max;
}
}

p = getenv( "FT2_ALLOC_COUNT_MAX" );
if ( p != NULL )
{
FT_Long  total_count = ft_atol( p );


if ( total_count > 0 )
{
table->bound_count     = 1;
table->alloc_count_max = (FT_ULong)total_count;
}
}

p = getenv( "FT2_KEEP_ALIVE" );
if ( p != NULL )
{
FT_Long  keep_alive = ft_atol( p );


if ( keep_alive > 0 )
table->keep_alive = 1;
}

result = 1;
}
}
return result;
}


extern void
ft_mem_debug_done( FT_Memory  memory )
{
FT_MemTable  table = (FT_MemTable)memory->user;


if ( table )
{
memory->free    = table->free;
memory->realloc = table->realloc;
memory->alloc   = table->alloc;

ft_mem_table_destroy( table );
memory->user = NULL;
}
}



static int
ft_mem_source_compare( const void*  p1,
     const void*  p2 )
{
FT_MemSource  s1 = *(FT_MemSource*)p1;
FT_MemSource  s2 = *(FT_MemSource*)p2;


if ( s2->max_size > s1->max_size )
return 1;
else if ( s2->max_size < s1->max_size )
return -1;
else
return 0;
}


extern void
FT_DumpMemory( FT_Memory  memory )
{
FT_MemTable  table = (FT_MemTable)memory->user;


if ( table )
{
FT_MemSource*  bucket = table->sources;
FT_MemSource*  limit  = bucket + FT_MEM_SOURCE_BUCKETS;
FT_MemSource*  sources;
FT_UInt        nn, count;
const char*    fmt;


count = 0;
for ( ; bucket < limit; bucket++ )
{
FT_MemSource  source = *bucket;


for ( ; source; source = source->link )
count++;
}

sources = (FT_MemSource*)ft_mem_table_alloc(
             table, sizeof ( *sources ) * count );

count = 0;
for ( bucket = table->sources; bucket < limit; bucket++ )
{
FT_MemSource  source = *bucket;


for ( ; source; source = source->link )
sources[count++] = source;
}

ft_qsort( sources, count, sizeof ( *sources ), ft_mem_source_compare );

printf( "FreeType Memory Dump: "
"current=%ld max=%ld total=%ld count=%ld\n",
table->alloc_current, table->alloc_max,
table->alloc_total, table->alloc_count );
printf( " block  block    sizes    sizes    sizes   source\n" );
printf( " count   high      sum  highsum      max   location\n" );
printf( "-------------------------------------------------\n" );

fmt = "%6ld %6ld %8ld %8ld %8ld %s:%d\n";

for ( nn = 0; nn < count; nn++ )
{
FT_MemSource  source = sources[nn];


printf( fmt,
source->cur_blocks, source->max_blocks,
source->cur_size, source->max_size, source->cur_max,
FT_FILENAME( source->file_name ),
source->line_no );
}
printf( "------------------------------------------------\n" );

ft_mem_table_free( table, sources );
}
}

#else  /* !FT_DEBUG_MEMORY */

/* ANSI C doesn't like empty source files */
typedef int _debug_mem_dummy;

#endif /* !FT_DEBUG_MEMORY */


/* END */
